package 力扣;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author yyq
 * @create 2022-06-18 9:33
 */
public class leetcode416 {



    public static void main(String[] args) {
        leetcode416 leetcode416=new leetcode416();
        System.out.println(leetcode416.canPartition(new int[]{2,2,1,1}));
    }
    public boolean canPartition(int[] nums) {
       int maxNum = Integer.MIN_VALUE;
       int sum = 0;
       int target = 0;
       for (int i=0;i<nums.length;i++){
           if(nums[i]>maxNum) maxNum=nums[i];
           sum = sum + nums[i];
       }
       target = sum/2;
       if(sum%2!=0) return false;
       if(maxNum>target) return false;
       if(maxNum==target) return true;
       int bag=target+1;
       int[][] dp=new int[nums.length][bag];

       // 初始化dp数组
        for (int j =0;j<bag;j++){
            if(nums[0] <= j){
                dp[0][j] = nums[0];
            }
            else dp[0][j] = 0;
        }

        for (int i=1;i<dp.length;i++){
            dp[i][0] = 0;
        }

        //完善dp数组
        for (int i =1;i<dp.length;i++){
            for (int j=1;j<bag;j++){
                if(nums[i]>j){
                    dp[i][j] = dp[i-1][j];
                }
                if(nums[i]<=j){
                    dp[i][j] = Math.max(dp[i-1][j],nums[i]+dp[i-1][j-nums[i]]);
                }
                if(dp[i][j]==target) return true;
                if(dp[i][j]>target) break;
            }
        }
        for (int i =0;i<dp.length;i++){
            for (int j=0;j<bag;j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return false;
    }


}
